In network communication, efforts to continuously improve the efficiency and security of network operation is an important goal for Internet users. Packet classification may distinguish or classify data packets based on multiple dimensions of information carried in packet headers, and thereby implement access control, traffic engineering, intrusion detection, and many other network services. More specifically, a network router may classify incoming packets into different flows and then to perform appropriate actions depending on the classification.
A packet classifier may use a set of filters or rules to specify packet classes. For example, a rule in an access control list (ACL) may specify a set of source and destination network address prefixes and associate a corresponding action with the rule (e.g., deny or permit access to a certain service or device). An ACL may comprise a set of rules applied to a variety of fields in a packet header, wherein each field is also called a dimension. For an example, for packets using Transport Layer Protocol (TCP), five dimensions including source port numbers, destination port numbers, source Internet Protocol (IP) network address prefixes, destination IP network address prefixes, and network protocols may be used. Various network services or devices, such as servers, routers, and switches, may be equipped with or subject to ACLs. For instance, in data center (DC) and cloud applications, packet classification and ACL may need to be performed at a high speed (e.g., on the order of tera bit per second), and latency in network ACL lookup may need to be low. The goal of high throughput may present a challenge for efficient implementation of packet classification algorithms.